// 注意点：
// 1. 就是n需要减1
// 2. 如果有一轮 没有互换过元素，则说明已经排好序了，可以提前结束循环
// 3. 自循环，长度大于2，则继续循环

import { testSort, measureSort} from "./utils";

function bubbleSort(arr: number[]): number[] {
  let n = arr.length;
  while (n > 1) {
    let swapped = false;
    for (let i = 0; i < n - 1; i++) {
      if (arr[i] > arr[i + 1]) {
        swapped = true;
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
      }
    }
    if (!swapped) break;
    n--;
  }

  return arr;
}

// 双循环方式
// function bubbleSort2(arr: number[]): number[] {
//   let n = arr.length;
//   for(let j = 0; j < n - 1; j++){
//     let swapped = false;
//     for(let i = 0; i< n-1-j; i++){
//       if(arr[i] > arr[i+1]){
//         swapped = true;
//         [arr[i], arr[i+1]] = [arr[i+1], arr[i]];
//       }
//     }
//     if(!swapped) break;
//   }

//   return arr;
// }

// 测试
testSort(bubbleSort);
// 测试时间
measureSort(bubbleSort, 100000);
